package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

/**
 * 层次遍历, 加右节点, O(1)空间
 * 巧妙利用已经加好的next指针记录遍历位置, 省去了队列, 只用O(1)空间
 *
 * @author tzp
 * @since 2020/9/14
 */
public class LC117_1 implements TreeProblem {
    public static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    ", next=" + next +
                    '}';
        }
    }

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        Node x = root;
        Node lonelyChild = null;
        Node firstChild = null;
        while (x != null) {
            if (lonelyChild != null) {
                if (x.left != null) {//左不空
                    lonelyChild.next = x.left;
                    if (x.right != null) {
                        x.left.next = x.right;
                        lonelyChild = x.right;
                    } else {
                        lonelyChild = x.left;
                    }
                } else if (x.right != null) {//左空 右不空
                    lonelyChild.next = x.right;
                    lonelyChild = x.right;
                }
            } else {
                if (x.left != null) {//左不空
                    if (x.right != null) {
                        x.left.next = x.right;
                        lonelyChild = x.right;
                    } else {
                        lonelyChild = x.left;
                    }
                } else if (x.right != null) {//左空 右不空
                    lonelyChild = x.right;
                }
            }

            if (firstChild == null) {
                firstChild = x.left != null ? x.left : x.right;
            }

            if (x.next != null) {
                x = x.next;
            } else if (firstChild != null) {
                x = firstChild;
                firstChild = null;
                lonelyChild = null;
            } else {
                break;
            }
        }

        return root;
    }

    public static void main(String[] args) {

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node7 = new Node(7);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.right = node7;

        System.out.println(new LC117_1().connect(node1));
    }
}
